iT邦幫忙

2023 iThome 鐵人賽

DAY 19
0
自我挑戰組

Lex & Yacc 學習筆記系列 第 19

[Day19] Yacc - 優先級(1) left & right

  • 分享至 

  • xImage
  •  

本篇內容

  • 介紹 Yacc語法中的優先級: left & right
  • 範例 - 簡易計算機4

優先級

我們從昨天的規則衝突中可以發現,部分衝突的發生原因,在於當字串組合可以被兩種以上的規則匹配時,系統不知道要匹配哪一項規則。因此,我們可以定義規則的階級差異,在發生衝突時,優先匹配位階較高的規則,便可以避免衝突發生。規則的階級定義有很多種方式,今天先來看看其中一種:left & right。

優先級(1) left & right

從昨天的例子,我們發現shift/reduce conflict主要發生在字串組同時匹配到shift跟reduce操作的時候。在做數值運算時,先做前面的運算或是先做後面的運算,運算結果有可能會有很大的不同。

在做連續加減法的運算時,在沒有括號的情況下,主要的運算方式為由左至右逐步計算。
因此,我們只要在符合運算的序列出現時,就優先做計算,便可以解決衝突的問題。

在Lex中,我們可以利用”left”(左相關)跟”right”(右相關)這兩個語法。來看下面這個例子:

1 + 2 + 3

在上面的式子中,兩個+號有相同的優先級。那哪個部分會先被運算呢?

如果是定義左相關,那就會由左向右運算。

%left '+'
// operation: (1 + 2) + 3

同理,若是定義右相關,那就會由右方先計算。

%right '+'
// operation: 1 + (2 + 3)

如此一來,衝突的問題就解決了。

接著,我們要讓計算機可以進行四則運算。四則運算有個重要的規則:先乘除後加減。然而若是按照下面這個寫法,加減乘除的規則位階相同,無法達成”先計算乘除法”的要求,且會造成規則衝突。

expr:
      NUMBER                { $$ = $1; }
    | expr '+' expr         { $$ = $1 + $3; }
    | expr '-' expr         { $$ = $1 - $3; }
    | expr '*' expr         { $$ = $1 * $3; }
    | expr '/' expr         { $$ = $1 / $3; }

因此,我們除了定義加減法之外,也要定義乘除法,並且比加減法具有更高的優先級。寫法如下:

%left '+' '-'
%left '*' '/'

若是有多個符號要被定義優先級,則後定義的符號具有較高的優先級。在上面的寫法中,”乘法與除法”比”加法與減法”具有較高的優先級。

到此,我們就定義好四則運算的兩大規則:

  1. 先乘除後加減
  2. 位階相同時,由左而右計算

範例 - 簡易計算機4

說明

請實作出一個簡易的計算機,能夠對多個正整數做四則運算(加減乘除),符合運算優先順序為小括號→乘除法→加減法,並回傳結果。

程式實作

Lex

  • 本次目標是實作四則運算,故有四種運算符號
  • 本次運算包含小括號,需要回傳其token
%{
#include "main.h"
#include "yacc.tab.h"
%}

posint      ([0-9]+)
blank_chars ([ \f\r\t\v]+)
expressions ([-+*/()])

%%

{posint}        { yylval = atoi(yytext); return NUMBER; }
{expressions}   { return yytext[0]; }
{blank_chars}   { ; }
"="             { return yytext[0]; }
\n              { ; }

%%

int yywrap(void) {
    return 1;
}

Yacc

  • 在Definition區塊新增優先級
  • 新增乘法與除法的Rules
  • 新增小括號的Rule
%{
#include "main.h"

void yyerror(const char *s);
extern int yylex();
extern int yyparse();

%}

%token NUMBER
%left '+' '-'
%left '*' '/'

%%

func:
      expr '='              { printf("Result: %d\n", $1); }
    ;

expr:
      NUMBER                { $$ = $1; }
    | expr '+' expr         { $$ = $1 + $3; }
    | expr '-' expr         { $$ = $1 - $3; }
    | expr '*' expr         { $$ = $1 * $3; }
    | expr '/' expr         { $$ = $1 / $3; }
    | '(' expr ')'          { $$ = $2; }
    ;

%%

void yyerror(const char *s) {
    cerr << s << endl;
}

執行結果

輸入內容

4 * 7 + 88 / 4 =

輸出結果

Result: 50

結語

今天我們介紹了優先級left & right,可以規範位階相同或不同時的規則匹配順位。

參考資料

  • Levine, John R., Tony Mason and Doug Brown [1992]. Lex & Yacc. O’Reilly & Associates, Inc. Sebastopol, California.
  • Tom Niemann. Lex & Yacc

上一篇
[Day18] Yacc - Ambiguity and Conflicts
下一篇
[Day20] Yacc - 優先級(2) nonassoc prec
系列文
Lex & Yacc 學習筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言